#include<algorithm>
using std::max;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

struct Height
{
    int left;
    int right;
    Height(): right(0), left(0) {}
};


class Solution {
private:
    int delimeter = 0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        nodeStatus(root);
        return delimeter;

    }

    Height nodeStatus(TreeNode* root) {
        Height h;
        if (root->left) {
            auto leftStatus = nodeStatus(root->left);
            h.left += max(leftStatus.left, leftStatus.right) + 1;
        }
        if (root->right) {
            auto rightStatus = nodeStatus(root->right);
            h.right += max(rightStatus.left, rightStatus.right) + 1;
        }
        delimeter = max(delimeter, h.left + h.right);
        return h;
    }

    
    

    
};